package pers.whj.sort;

import java.lang.reflect.Array;

public class MergeSort<T> extends Sort<T> {
    public MergeSort(T[] data) throws SortException {
        super(data);
    }

    public MergeSort(T[] data, Compare<T> compare) throws SortException {
        super(data, compare);
    }

    @Override
    public void sort(int left, int right) throws SortException {
        sort(mData, mCompare, left, right);
    }

    public static <E> void sort(E[] data) throws SortException {
        sort(data, null);
    }

    public static <E> void sort(E[] data, Compare<E> compare) throws SortException {
        sort(data, compare, 0, data == null ? 0 : data.length - 1);
    }

    public static <E> void sort(E[] data, Compare<E> compare, int left, int right) throws SortException {
        check(data, compare, left, right);
        mergeSort(data, compare, left, right);
    }

    private static <E> void mergeSort(E[] data, Compare<E> compare, int left, int right) {
        if (left < right) {
            int mid = (right + left) / 2;
            mergeSort(data, compare, left, mid);
            mergeSort(data, compare, mid + 1, right);
            merge(data, compare, left, mid, right);
        }
    }

    private static <E> void merge(E[] data, Compare<E> compare, int left, int mid, int right) {
        E[] temp = (E[]) Array.newInstance(data[0].getClass(), right - left + 1);
        if (right - left + 1 >= 0) {
            System.arraycopy(data, left, temp, 0, right - left + 1);
        }
        int s1 = 0;
        int s2 = mid - left + 1;
        int t = left;
        while (s1 <= mid - left && s2 <= right - left) {
            if (compare.swap(temp[s1], temp[s2])) {
                data[t++] = temp[s2++];
            } else {
                data[t++] = temp[s1++];
            }
        }
        while (s1 <= mid - left) {
            data[t++] = temp[s1++];
        }
        while (s2 <= right - left) {
            data[t++] = temp[s2++];
        }
    }
}